package ljl.alg.jianzhioffer.round3.medium;

import java.util.*;

public class _48_lengthOfLongestSubstring {

    class my {
        public int lengthOfLongestSubstring(String s) {
            if (s == null || s.length() == 0) return 0;
            int max = 1;
            Queue<Character> q = new LinkedList<>();
            Set<Character> set = new HashSet<>();
            for (char c : s.toCharArray()) {
                q.offer(c);
                while (set.contains(c)) {
                    char left = q.poll();
                    set.remove(left);
                    if (left == c) {
                        break;
                    }
                }
                set.add(c);
                max = Math.max(max, set.size());
            }
            return max;
        }
    }

    class lufei {
        public int lengthOfLongestSubstring(String s) {
            Map<Character, Integer> dic = new HashMap<>();
            int res = 0, tmp = 0;
            for(int j = 0; j < s.length(); j++) {
                int i = dic.getOrDefault(s.charAt(j), -1);
                dic.put(s.charAt(j), j);
                tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
                res = Math.max(res, tmp);
            }
            return res;
        }
    }


    /**
     * 不聪明这个解法
     * */
    @Deprecated
    class lufei_linear_search {
        public int lengthOfLongestSubstring(String s) {
            int res = 0, tmp = 0;
            for(int j = 0; j < s.length(); j++) {
                int i = j - 1;
                while(i >= 0 && s.charAt(i) != s.charAt(j)) i--; // 线性查找 i
                tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
                res = Math.max(res, tmp);
            }
            return res;
        }
    }

    class lufei_shuang_zhi_zhen {
        public int lengthOfLongestSubstring(String s) {
            Map<Character, Integer> dic = new HashMap<>();
            int i = -1, res = 0;
            for(int j = 0; j < s.length(); j++) {
                if(dic.containsKey(s.charAt(j)))
                    i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i
                dic.put(s.charAt(j), j);
                res = Math.max(res, j - i);
            }
            return res;
        }
    }

}
